1. Field of the Invention
The present invention relates to processor-based implementations of mathematical functions and, more specifically but not exclusively, to coordinate rotation digital computer (CORDIC) processing.
2. Description of the Related Art
This section introduces aspects that may help facilitate a better understanding of the invention. Accordingly, the statements of this section are to be read in this light and are not to be understood as admissions about what is prior art or what is not prior art.
The CORDIC algorithm, also referred to as the digit-by-digit method or Volder's algorithm, is a hardware-efficient iterative bound convergence method for solving trigonometric and other mathematical functions. Using the CORDIC algorithm, elementary functions can be realized just by table look-up, shift, and add operations, which make the CORDIC algorithm very attractive for hardware implementations.
Assuming a vector (Xi,Yi) rotates by an angle αi and arrives at (Xi+1, Yi+1) in the Cartesian plane, the angular rotation can be described by Equations (1) and (2) as follows:Xi+1=Xi cos αi−Yi sin αi=cos αi(Xi−Yi tan αi)  (1)Yi+1=Yi cos αi+Xi sin αi=cos αi(Yi+Xi tan αi)  (2)If the rotation angle is restricted such that tan αi=±2−i, then the multiplication by the tangent can be reduced to a simple shift operation.
FIG. 1 graphically shows how a pseudo-rotation produces a vector with the same angle as the rotated vector, but with a length given by Equation (3) as follows:Ri+1=Ri/cos αi  (3)
With the above analysis, the classical CORDIC functions in each iteration i of circular rotation mode assuming pseudo-rotation are given by Equations (4)-(6) as follows, where Z stands for θ:Xi+1=Xi−diYi2−i  (4)Yi+1=Yi+diXi2−i  (5)Zi+1=Zi−di arctan(2−i), di=sign(Zi){−1,1}  (6)
Considering a series of n pseudo-rotations, the vector magnitude increases by a factor of 1/K, where K=π cos(arctan(2−i)). The coordinates (Xn, Yn) after this series of n pseudo-rotations are given by:Xn=1/K(X0 cos θ−Y0 sin θ)  (7)Yn=1/K(Y0 cos θ+X0 sin θ)  (8)
If the initial values of X0 and Y0 are chosen to be K and 0, respectively, and Z0 is initialized to angle θ, then, after a predetermined set of pseudo-rotations determined by arctan(2−i), Xn and Yn converge to cosine and sine components of the angle θ as Z converges to zero.
In general, to achieve n bits of precision, n pre-computed rotation angles (arctan(2−i)) are stored in a look-up table (LUT) and n CORDIC iterations perform Equations (4)-(6). High accuracy demands a large number of iterations to be performed, and the main challenge is to reduce the number of iterations and thus speed up the computation process.
The double-step CORDIC method combines two classical CORDIC angle rotations (iterations) into a single step. It was originally proposed for redundant binary signed digit (BSD) arithmetic as an enhancement over the branching CORDIC method.